package org.example.DataStructure.DoubleLinkedList;

import org.example.DataStructure.LinkList.LinkList;

import java.util.Iterator;

//双向链表的实现
public class DoubleLinkedList<T> implements Iterable<T> {
    //成员变量
    private Node<T> head;
    private Node<T> tail;
    private int size;

    //节点内部类
    private static class Node<T> {
        //成员变量,节点的数据，前驱指针和后继指针
        private T data;
        private Node<T> pre;
        private Node<T> next;

        //构造方法
        //直接传入数据的构造方法
        public Node(T data) {
            this.data = data;
            this.pre = null;
            this.next = null;
        }

        //传入三个参数的构造函数
        public Node(T data, Node<T> pre, Node<T> next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }
    }

    //构造方法
    public DoubleLinkedList() {
        //初始化头节点和尾节点
        this.head = new Node<T>(null, null, null);
        this.tail = null;
        //初始化链表的长度
        this.size = 0;
    }

    //空置链表
    public void clear() {
        this.head.next = null;
        this.tail = null;
        this.size = 0;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return this.size == 0;
    }

    //获取链表中元素的个数
    public int length() {
        return this.size;
    }

    //读取并返回第i个元素的值
    public T get(int i) {
        Node<T> node = this.head.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return node.data;
    }

    //在链表中添加一个元素
    public void insert(T t) {
        //如果链表为空
        if (isEmpty()) {
            //创建新的节点
            Node<T> newNode = new Node<>(t, head, null);
            //让新节点成为尾节点
            tail = newNode;
            //让头节点指向尾节点
            head.next = newNode;
        } else {
            //如果链表不为空
            //创建新节点
            Node<T> newNode = new Node<>(t, tail, null);
            //当前尾节点指向新节点
            tail.next = newNode;
            //让新节点成为尾节点
            tail = newNode;
        }
        //元素个数+1
        this.size++;
    }

    //在链表指定位置添加一个元素
    public void insert(int i, T t) {
        //找到i位置的前一个节点
        Node<T> pre = head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }
        //找到i位置的节点
        Node<T> current = pre.next;
        //创建新节点
        Node<T> newNode = new Node<>(t, pre, current);
        //让i位置的前一个节点的下一个节点赋值给新节点
        pre.next = newNode;
        //让i位置的下一个节点的前一个指针指向新节点
        current.next.pre = newNode;
        //元素个数+1
        this.size++;
    }

    //删除并返回线性表中第i个元素
    public T remove(int i) {
        //找到前一个节点
        Node<T> pre = this.head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }
        //找到i位置的节点
        Node<T> current = pre.next;
        //找到下一个节点
        Node<T> next = current.next;
        //前一个节点指向后一个节点，后一个节点指向前一个节点
        pre.next = next;
        next.pre = pre;
        //减少链表长度
        this.size--;
        //返回被删除的第i个节点
        return current.data;
    }

    //返回线性表中指定元素出现的第一个位置的索引，如果没有就返回-1
    public int indexOf(T t) {
        Node<T> node = this.head.next;
        for (int index = 0; node.next != null; index++) {
            if (node.data == t) {
                return index;
            }
        }
        return -1;
    }

    //获取第一个元素
    public T getFirst() {
        if (isEmpty()) {
            return null;
        }
        return head.next.data;
    }

    //获取最后一个元素
    public T getLast() {
        if (isEmpty()) {
            return null;
        }
        return tail.data;
    }

    //实现遍历方法
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node<T> current = head;

            @Override
            public boolean hasNext() {
                return current.next != null;
            }

            @Override
            public T next() {
                current = current.next;
                return current.data;
            }
        };
    }

    //重写ToString方法
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        DoubleLinkedList.Node<T> current = this.head;
        while (current != null) {
            sb.append(current.data);
            current = current.next;
            if (current != null) {
                sb.append(" <-> ");
            }
        }
        return sb.toString();
    }
}
